/**
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
 

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
 
进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题
 */

/**
 * 解法1
 * @description 按正负数拆分数组，分别遍历两个数组，然后比较生成新的非递减顺序数组
 * @param nums
 * @returns
 */
function splitSortedSquares(nums: number[]): number[] {
    const orgNegArr = nums.filter((n) => n < 0);
    const posiArr = nums.filter((n) => n >= 0);
    const turnNegArr = orgNegArr.reverse().map((n) => Math.abs(n));
    let pointN = 0;
    let pointP = 0;
    // 全是正整数
    if (orgNegArr.length < 1) {
        return nums.map((n) => n * n);
    } else if (posiArr.length < 1) {
        // 全是负数则直接返回倒转数组的平方即可
        return turnNegArr.map((n) => n * n);
    }

    const retArr = [];
    for (let i = 0; i < nums.length; i++) {
        if (
            posiArr[pointP] < turnNegArr[pointN] ||
            pointN > turnNegArr.length - 1
        ) {
            retArr.push(posiArr[pointP++]);
        } else {
            retArr.push(turnNegArr[pointN++]);
        }
    }
    return retArr.map((n) => n * n);
}

/**
 * 解法2
 * @description 头尾双指针，遍历比较
 * @param nums
 * @returns
 */
function sortedSquares(nums: number[]): number[] {
    // 头指针
    let L = 0;
    // 尾部指针
    let R = nums.length - 1;
    // 最终结果数组
    const retArr = [];
    // 移动头尾指针进行遍历
    while (L !== R) {
        // 将平方数较大的数插入结果数组尾部，并移动该数的指针
        if (Math.pow(nums[L], 2) < Math.pow(nums[R], 2)) {
            retArr.unshift(Math.pow(nums[R--], 2));
        } else {
            retArr.unshift(Math.pow(nums[L++], 2));
        }
    }
    // 将头尾指针相遇后的数(平方后最小的数)unshift进数组
    retArr.unshift(Math.pow(nums[L], 2));
    return retArr;
}

export { sortedSquares };
